package leetcode_100;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;


/**
 *@author 周杨
 *CombinationSum_39  Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

				The same repeated number may be chosen from candidates unlimited number of times.

Note:

All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.
 *describe: 回朔法解决 
 *2018年4月26日 上午9:44:34
 */
public class CombinationSum_39 {

	public static void main(String[] args) {
	/*	CombinationSum_39 clazz=new CombinationSum_39();
	
		List<List<Integer>> res = clazz.combinationSum1(new int[] { 2,3,6,7 }, 7);*/

	}
	
	/**
	 * describe:深搜 已经剪枝
	 * 2018年12月24日 下午8:55:58
	 */
	public List<List<Integer>> combinationSum1(int[] candidates, int target) {
		List<List<Integer>> res=new ArrayList<List<Integer>>();
		if(target<=0) return res;
		Arrays.sort(candidates);
		dfs(res,new ArrayList<Integer>(),candidates,0,target);
		return res;
	}
	
	public void dfs(List<List<Integer>> res,List<Integer> temp,int []candidates,int index,int sum) {
		if(sum==0) {
			List<Integer> t=new ArrayList<Integer>(temp.size());
			t.addAll(temp);	
			res.add(t);
			return ;
		}
		if(sum<candidates[index])
			return ;
		for(int i=index;i<candidates.length;++i) {
			temp.add(candidates[i]);
			dfs(res,temp,candidates,i,sum-candidates[i]);
			temp.remove(temp.size()-1);
		}
	}
	

	int n;
	int nums[];
	List<List<Integer>> result;

	// 当前集合，当前使用的数字位置，当前还剩多少
	public void find(List<Integer> values, int index, int reserve) {
		if (reserve == 0) {
			ArrayList<Integer> item = new ArrayList<Integer>();
			item.addAll(values);
			result.add(item);
		} else {
			for (int i = index; i < n; i++) {// 遍历当前候选数组
				if (nums[i] <= reserve) {// 如果当前数小于目标值 将其加入备选方案中
					values.add(nums[i]);
					find(values, i, reserve - nums[i]);
					values.remove(values.size() - 1);
				}
			}
		}
	}

	public List<List<Integer>> combinationSum(int[] candidates, int target) {
		// 排序然后去除重复的
		Arrays.sort(candidates);
		// 去除重复，这样省心
		int i, n;
		n = 1;
		for (i = 1; i < candidates.length; i++) {
			if (candidates[i] != candidates[i - 1]) {
				candidates[n++] = candidates[i];
			}
		}
		this.nums = candidates;
		this.n = n;// 有几个不重复的数
		this.result = new ArrayList<List<Integer>>();
		find(new ArrayList<Integer>(), 0, target);
		return this.result;

	}
}
